package leetcode.Hot100;

import leetcode.TreeNode;
import leetcode.TreeNodeUtil;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Cheng Jun
 * Description: 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 有效 二叉搜索树定义如下：
 * <p>
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/6 20:08
 * 必须二刷，面试题
 */
public class isValidBST {


    long val = Long.MIN_VALUE;

    // 思路有问题，解法错误
    // 思路分析：node.val > node.left.val, node.val < node.right.val，但是还要考虑子树的节点值

    public static void main(String[] args) {
        TreeNode c = TreeNodeUtil.getBT(new Object[]{4, 2, 6, 1, 4, 5, 7});
        System.out.println(isValidBST1(c));
    }

    // 假设isValidBST 具有 判断该节点作为 根节点时，该节点树是否为二叉搜索树的功能
    // 要判断 该节点树是否为 BST，就要先验证 node.left, node.right 是否为 BST
    static boolean isValidBST(TreeNode root) {
        //     4
        //  2     6
        // 1  3  5 7
        // 当节点为null 即空树，则为二叉搜索树
        if (root == null) return true;
        // 如果能成为二叉搜索树，首先左右子树必须是二叉搜索树
        boolean isValid = isValidBST(root.left) && isValidBST(root.right);
        if (root.left != null) {
            isValid = root.val > root.left.val && isValid;
        }
        if (root.right != null) {
            isValid = root.val < root.right.val && isValid;
        }
        return isValid;
    }

    // 如果是二叉搜索树，那么中序遍历一定是升序的。
    static boolean isValidBST1(TreeNode root) {
        Deque<Integer> valueDeque = new LinkedList<>();
        inorderTraversalRec(root, valueDeque);
        int preValue = valueDeque.poll();
        while (!valueDeque.isEmpty()) {
            int curValue = valueDeque.poll();
            if (curValue > preValue) {
                preValue = curValue;
            } else {
                return false;
            }
        }
        return true;
    }

    // 中序遍历
    static void inorderTraversalRec(TreeNode root, Deque<Integer> res) {
        if (root == null) return;
        inorderTraversalRec(root.left, res);
        res.add(root.val);
        inorderTraversalRec(root.right, res);
    }

    // 优化中序遍历思路
    boolean isValidBST2(TreeNode root) {
        if (root == null) return true;
        boolean left = isValidBST2(root.left);
        if (root.val > val) {
            val = root.val;
        } else {
            return false;
        }
        boolean right = isValidBST2(root.right);
        return left && right;
    }

}
